import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by zhourh on 2018/7/27.
 *
 * 给定一个N叉树，找到其最大深度。

 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

 例如，给定一个 3叉树 :





 我们应返回其最大深度，3。

 说明:

 树的深度不会超过 1000。
 树的节点总不会超过 5000。
 */
public class MaximumDepthOfNAaryTree {

    public static void main(String[] args) {
        Node root = new Node();
        root.val = 1;
        Node node2 = new Node();
        node2.val = 2;
        Node node3 = new Node();
        node2.val = 3;
        Node node4 = new Node();
        node2.val = 4;
        Node node5 = new Node();
        node2.val = 5;
        Node node6 = new Node();
        node2.val = 6;
        List<Node> level2 = new ArrayList<>();
        level2.add(node2);
        level2.add(node3);
        level2.add(node4);
        root.children = level2;
        List<Node> level3 = new ArrayList<>();
        level3.add(node5);
        level3.add(node6);
        node3.children = level3;

        System.out.println(new MaximumDepthOfNAaryTree().maxDepth(root));

    }

    public int maxDepth2(Node root) {
        if (root == null) {
            return 0;
        }

        Stack<Node> stack = new Stack<>();
        List<Node> popNodes = new ArrayList<>();
        stack.push(root);
        int depth = 0;
        while (!stack.isEmpty()) {
            popNodes.clear();
            depth++;
            while (!stack.isEmpty()) {
                Node node = stack.pop();
                if (node != null && node.children != null) {
                    popNodes.addAll(node.children);
                }
            }
            if (!popNodes.isEmpty()) {
                for (Node childNode : popNodes) {
                    stack.push(childNode);
                }
            }
        }
        return depth;
    }

    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }

        int depth = 0;

        if (root.children != null) {
            for (Node node : root.children) {
                depth = Math.max(depth, maxDepth(node));
            }
        }

        return depth + 1;
    }

}
